#include <bits/stdc++.h>

using namespace std;

// ysh'smethod pass 52/73
//  class Solution
//  {
//  public:
//      struct point
//      {
//          point(int x, int y)
//          {
//              nums_0 = x;
//              nums_1 = y;
//          }
//          int nums_0;
//          int nums_1;
//      };
//      int findMaxForm(vector<string> &str, int m, int n)
//      {
//          vector<point> object;
//          for (auto s : str)
//          {
//              int num_0 = 0;
//              int num_1 = 0;
//              for (auto ch : s)
//              {
//                  if (ch == '0')
//                  {
//                      num_0++;
//                  }
//                  else
//                  {
//                      num_1++;
//                  }
//              }
//              point obj(num_0, num_1);
//              object.push_back(obj);
//          }
//          vector<point> all_point;
//          for (int i = 0; i <= m; i++)
//          {
//              for (int j = 0; j <= n; j++)
//              {
//                  point ex(i, j);
//                  all_point.push_back(ex);
//              }
//          }
//          vector<int> dp(all_point.size(), 0);
//          for (int i = 0; i < (int)object.size(); i++)
//          {
//              for (int j = (int)all_point.size() - 1; j >= 0; j--)
//              {
//                  if (all_point[j].nums_0 >= object[i].nums_0 && all_point[j].nums_1 >= object[i].nums_1)
//                  {
//                      int find_nums_0 = all_point[j].nums_0 - object[i].nums_0;
//                      int find_nums_1 = all_point[j].nums_1 - object[i].nums_1;
//                      int index = 0;
//                      for (int k = 0; k < (int)all_point.size(); k++)
//                      {
//                          if (all_point[k].nums_0 == find_nums_0 && all_point[k].nums_1 == find_nums_1)
//                          {
//                              index = k;
//                              break;
//                          }
//                      }
//                      dp[j] = max(dp[j], dp[index] + 1);
//                  }
//              }
//          }
//          return dp[all_point.size() - 1];
//      };
//  };

class Solution
{
public:
    int findMaxForm(vector<string> &strs, int m, int n)
    {
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (auto s : strs)
        {
            int nums_zero = 0;
            int nums_one = 0;
            for (auto ch : s)
            {
                if (ch == '0')
                {
                    nums_zero++;
                }
                else
                {
                    nums_one++;
                }
            }
            for (int i = m; i >= nums_zero; i--)
            {
                for (int j = n; j >= nums_one; j--)
                {
                    dp[i][j] = max(dp[i][j], dp[i - nums_zero][j - nums_one] + 1);
                }
            }
        }
        return dp[m][n];
    }
};

int main()
{
    vector<string> strs{
        "10",
        "0001",
        "111001",
        "1",
        "0"};
    Solution sol;
    cout << sol.findMaxForm(strs, 4, 3) << endl;
    return 0;
}